package com.gong.suanfa.BFPRT;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/13 0013 10:24
 */
public class Bfprt {

    public static void main(String[] args) {
        int[] arr = {0,8,2,5,7,4,3,6,1,9};
        for (int i = 0; i < 10; i++) {
            int findindex = findindex(arr, i+1, 0, 9);
            System.out.println(findindex);
        }
    }

    public static int findindex(int[] arr,int target,int left,int right){
        //确定分组
        int hua = (right-left+1)/5;
        int[] zhong = new int[hua];//中位数数组
        for (int i = 0; i < hua; i++) {
            zhong[i] = findzhong(arr,left+i*5,left+i*5+4);
        }
        //确定中位数数组中的中位数
        int findzhong = arr[left];
        if (zhong!=null && zhong.length !=0){
            findzhong = findzhong(zhong, 0, zhong.length - 1);
        }

        //按照findzhong划分数组
        int l = left-1;
        int r = right+1;
        int index = left;
        while (index < r && l<r){
            if (arr[index] < findzhong){
                swap(arr,index,l+1);
                l++;
                index++;
            }else if (arr[index] == findzhong){
                index++;
            }else {
                swap(arr,index,r-1);
                r--;
            }
        }
        //根据目标是第几大小来找
        int min = l-left+1;//左边有多少个值
        if (min+1 < target){
            return findindex(arr,target-min-1,l+2,right);
        }else if (min+1 == target){
            return arr[l+1];
        }else {
            return findindex(arr,target,left,l);
        }
    }

    //寻找中位数
    private static int findzhong(int[] arr, int left, int right) {
        for (int i = left+1; i < right+1; i++) {
            int j = i-1;
            while (j>=left){
                if (arr[j+1] > arr[j]){
                    swap(arr,j+1,j);
                }
                j--;
            }
        }

        if ((right-left)%2 == 0){//是奇数
            return arr[left+(right-left)/2];
        }else {
            return arr[left+(right-left)/2]>arr[left+(right-left)/2+1]?arr[left+(right-left)/2+1]:arr[left+(right-left)/2];
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
